/*
 * @lc app=leetcode.cn id=40 lang=golang
 *
 * [40] 组合总和 II
 */

// @lc code=start
func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	tmp := make([]int, 0, len(candidates))
	res := make([][]int, 0)
	var backing func(pos int, rest int)
	backing = func(pos, rest int) {
		if rest == 0 {
			t := make([]int, len(tmp))
			copy(t, tmp)
			res = append(res, t)
			return
		}
		if pos >= len(candidates) || candidates[pos] > rest || rest < 0 {
			return
		}

		for i := pos; i < len(candidates); i++ {
			if i-1 >= pos && candidates[i] == candidates[i-1] {
				continue
			}
			tmp = append(tmp, candidates[i])
			backing(i+1, rest-candidates[i])
			tmp = tmp[:len(tmp)-1]
		}
		return
	}

	backing(0, target)
	return res
}

// @lc code=end

